class Solution {
public:
    vector<int> partitionLabels(string s) {
        int hash[26] = { 0 }, n = s.size();

        // hash数组记录的是每种字符出现的最远距离
        for(int i = 0; i < n; i++)
            hash[s[i] - 'a'] = i;

        int left = 0, right = -0x3f3f3f3f;
        vector<int> ret;

        for(int i = 0; i < n; i++)
        {
            right = max(right, hash[s[i] - 'a']);
            
            // 当i == right时，表示i此时已经走到包含所有相同字符的最远距离了
            // 此时收获结果，left置为i + 1
            if(i == right)
            {
                ret.push_back(i - left + 1);
                left = i + 1;
            }
        }
        return ret;
    }
};